/**
 * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，
 * 分别表示 nums1 和 nums2 中的元素数目。
 * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
 * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
 * 为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，
 * 后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
*/
#if  1
#include <stdio.h>
#include <stdlib.h>
//数组的输出
void printfArray(int *nums,int len)
{
    for (int i = 0; i < len; i++)
    {
        /* code */
        printf("%d ",nums[i]);
    }
    printf("\n");
}
//方法一：双指针
void merge2(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int p1 = 0, p2 = 0;
    int sorted[m + n];
    int cur;
    while (p1 < m || p2 < n) {
        if (p1 == m) {
            cur = nums2[p2++];
        } else if (p2 == n) {
            cur = nums1[p1++];
        } else if (nums1[p1] < nums2[p2]) {
            cur = nums1[p1++];
        } else {
            cur = nums2[p2++];
        }
        sorted[p1 + p2 - 1] = cur;
    }
    for (int i = 0; i != m + n; ++i) {
        nums1[i] = sorted[i];
    }
}

//方法二：将2数组放到1中  代码量有太大 在排序
int cmp(int* a, int* b) {
    return *a - *b;
}

void merge1(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    for (int i = 0; i != n; ++i) {
        nums1[m + i] = nums2[i];
    }
    qsort(nums1, nums1Size, sizeof(int), cmp);
}
//方法三：利用两个指针  如果遇到相同的那就将相同的 或者比1数组中的大的下一位放到2数组的当前位置 
// 0           1        2         3
//1 2 3 7   1 2 2 7   1 2 2 3   1 2 2 3 0 0 7
//2 5 6     3 5 6     7 5 6     5 6

// i = 0 j = 0 i = 1 j = 0 i = 2 j = 0  i = 3 j = 1
// 1 2 3       1 2 2       1 2 2 3      1 2 2 3 5
// 2 5 6       3 5 6       3 5 6        2 5 6
//始终没看懂为啥这个会报错
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int index = 0;
    int i = 0; //控制nums1的数值索引值
    int j = 0; //控制nums2的数组索引值
    int temp = 0; // 用于交换的值
    while ( j < n)
    {
        /* code */
        if (nums2[j] <= nums1[i] && i < m - 1)
        {
            /* code */
            temp = nums2[j];
            nums2[j] = nums1[i + 1];
            nums1[i + 1] = temp;
        }
        
        if (nums2[j] > nums2[j + 1] && i >= m - 1)
        {
            /* code */
            nums1[m + n - 1] = nums2[j];
        }
        if(nums2[j] <= nums2[j + 1] && i >= m - 1)
        {
            nums1[i + 1] = nums2[j];
        }
        if (i >= m - 1)
        {
            /* code */
            j++;
        }
        i++;
    }
}
//逆向双指针

void merge3(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int p1 = m - 1, p2 = n - 1;
    int tail = m + n - 1;
    int cur;
    while (p1 >= 0 || p2 >= 0) {
        if (p1 == -1) {
            cur = nums2[p2--];
        } else if (p2 == -1) {
            cur = nums1[p1--];
        } else if (nums1[p1] > nums2[p2]) {
            cur = nums1[p1--];
        } else {
            cur = nums2[p2--];
        }
        nums1[tail--] = cur;
    }
}

int main()
{
    int nums1[] = {1,2,3,3,0,0,0};
    int nums2[] = {2,5,6};
    int length1  = sizeof(nums1) / sizeof(int);
    int length2  = sizeof(nums2) / sizeof(int);
    int m = 4;
    int n = 3;
    merge3(nums1,length1,m,nums2,length2,n);
    for (int i = 0; i < length1; i++)
    {
        /* code */
        printf("%d ",nums1[i]);
    }
    
    return 0;
}
#endif